package pl.edu.agh.gt.ga;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import org.apache.log4j.Logger;

import pl.edu.agh.gt.gui.ChartDisplay;
import pl.edu.agh.gt.util.BetterRandom;
import pl.edu.agh.gt.util.Utils;

public class Population {

	private final static Logger log = Logger.getLogger(Population.class);

	/** 
	 * Order is shuffled during execution 
	 * The SORTED order should be maintained BETWEEN reinsertion and mutation phase 
	 */
	private LinkedList<Individual> individuals; 
	private boolean sortIndicator = false;
	
	private final ExecutorService threadPool = Executors.newFixedThreadPool(4);
	private List<IndividualEvaluationTask> tasks;

	private final FitnessFunction fitnessFun;
	private final MutationOperator mutationOp;
	private final CrossbreedOperator crossbreadOp;
	private final Initializer initializer;

	private Parameters params;
	
	private PopulationListener listener;

	/** runtime variables */
	private int iteration;
	private PopulationStats stats;

	public Population(Parameters params, Initializer initializer, FitnessFunction fitness, MutationOperator mutation,
			CrossbreedOperator xbreed) {
		stats = new PopulationStats();
		this.params = params;
		fitnessFun = fitness;
		this.initializer = initializer;
		crossbreadOp = xbreed;
		this.mutationOp = mutation;
		Individual.deathCounterInit = params.deathCounterInit;
		tasks = new ArrayList<IndividualEvaluationTask>(params.initialPopulationSize * 2);
	}

	private class IndividualEvaluationTask implements Callable<Float> {

		private final Individual ind;
		private final Parameters params;

		public IndividualEvaluationTask(Individual i, Parameters p) {
			ind = i;
			params = p;
		}

		@Override
		public Float call() throws Exception {
			ind.fitness = fitnessFun.estimate(ind.genotype, params);
			return ind.fitness;
		}
		
		public Individual getIndividual () {
			return ind;
		}
	}

	private void mutation() throws InterruptedException {

		tasks.clear();

		// individuals should be sorted here!
		assert sortIndicator == true : "Individuals not sorted!";
		
		int pos = 0;
		for (Individual ind : individuals) {

			float mutationProbability = params.mutationFactor;
			// reduce probability of mutation for well fitted individuals
			mutationProbability *= Math.pow(1.0 - ((float)pos / (float)individuals.size()), 0.4);

			if (BetterRandom.nextFloat("mp") < mutationProbability) {
				if(ind.id == stats.bestIndividual.id )
					log.warn(" -------- Mutating best individual ! -------- ");
				
				ind.genotype = mutationOp.mutate(ind.genotype, params);
				addEvalTask(ind);
			}
			
			pos++;
		}
		
		/* Watch out! Forking here */
		threadPool.invokeAll(tasks);
		
		// fitness changed, order expired
		sortIndicator = false;
		
		log.info("Mutated "+tasks.size()+" inds");
		
		// announce to listeners
		for(IndividualEvaluationTask task : tasks) {
			Individual ind = task.getIndividual();
			if( ind.listener != null)
				ind.listener.onCrossbreed(ind);
		}
	}

	private void crossbreed() throws InterruptedException {

		tasks.clear();

		// currently - 2 children from 2 parents
		List<Individual> parents = tournamentSelection(
				(int) 2.0 * Math.round(individuals.size() * params.crossbreedFactor), false);

		Iterator<Individual> it = parents.iterator();
		while (it.hasNext()) {

			Individual parent1 = it.next();
			if (!it.hasNext())
				break;
			Individual parent2 = it.next();

			Genotype newGens1 = crossbreadOp.crossbreed(parent1.genotype, parent2.genotype, params);
			Genotype newGens2 = crossbreadOp.crossbreed(parent1.genotype, parent2.genotype, params);

			Individual newborn1 = new Individual(newGens1);
			Individual newborn2 = new Individual(newGens2);
			addEvalTask(newborn1);
			addEvalTask(newborn2);
			
			sortIndicator = false;
			individuals.add(newborn1);
			individuals.add(newborn2);
		}

		/* Watch out! Forking here */
		threadPool.invokeAll(tasks);
		
		log.info("XBreed "+tasks.size()+" inds");
		
		// announce to listeners
		for(IndividualEvaluationTask task : tasks) {
			Individual ind = task.getIndividual();
			if( ind.listener != null)
				ind.listener.onCrossbreed(ind);
		}
	}

	private void reinsertion() {

		// decrease life
		// remove dead individuals
		
		Collections.sort(individuals);
		sortIndicator = true;
		
		removeDuplicates(individuals);
		
		int oversize = individuals.size() - params.initialPopulationSize;

		Iterator<Individual> iter = individuals.iterator();
		for (int i = 0; i < oversize; i++) {
			Individual l = iter.next();
			l.deathCounter--;
			
			if(l.listener!=null)
				l.listener.onDecreaseLifetime(l);
			
			if (l.deathCounter <= 0) {
				
				if(l.listener!=null)
					l.listener.onRemove(l);
				
				iter.remove();
			}
		}

	}
	
	private void removeDuplicates(List<Individual> inds) {
		log.debug("Removing dups");
		List<Individual> dups = Utils.removeDuplicatesFromList(inds, Individual.class);
		for(Individual i : dups)
			if(i.listener != null)
				i.listener.onRemove(i);
		log.debug("Removed "+dups.size()+" duplicates");
	}

	/**
	 * Tournament selection of N individuals (best or worse)
	 */
	private List<Individual> tournamentSelection(int winnersSetSize, boolean inverse) {

		List<Individual> winners = new ArrayList<Individual>();

		Collections.shuffle(individuals, BetterRandom.getInstance("ts"));
		sortIndicator = false;

		float tournamentSize = ((float) individuals.size() / winnersSetSize);
		float endIdx = tournamentSize;

		ListIterator<Individual> iter = individuals.listIterator();
		Individual winner = iter.next();

		while (iter.hasNext()) {

			if (iter.nextIndex() == (int) Math.round(endIdx)) {
				winners.add(winner);
				winner = iter.next();
				endIdx += tournamentSize;
			}

			Individual curr = iter.next();

			if (inverse) {
				if (curr.fitness < winner.fitness)
					winner = curr;
			} else {
				if (curr.fitness > winner.fitness)
					winner = curr;
			}

		}

		return winners;
	}

	private void addEvalTask(final Individual ind) {

		tasks.add(new IndividualEvaluationTask(ind, params));
	}

	public void initializePopulation() throws Exception {

		individuals = initializer.initialize(params);
		evaluatePopulation();
		iteration = 0;
		if(listener != null)
			listener.onPopulationInitialized(this);
	}
	
	public void evolvePopulation() throws Exception {
		evolvePopulation(params.maxIterations);
	}

	public void evolvePopulation(int iterCount) throws Exception {

		iterCount += iteration;
		
		// XXX warunek stopu gdy fitness sie stabilizuje ?
		// moze gdy histogram sie zmienia na 'nienormalny' - semiwariancja
		// dodatnia ~ 0
		while (iteration < iterCount) {

			// mutate
			mutation(); // loose order

			// X breed
			crossbreed();

			// selection & reinsertion
			reinsertion(); // become ordered

			// diagnostics ...
			calculateStats();
			
			// announce to listener
			if(listener != null)
				listener.onIterationDone(this);
			
			log.info("iter: " + iteration + "\t" + stats);

			iteration++;
		}
		
		if(listener != null)
			listener.onEvolutionFinished(this);
		
	}

	public void diag() throws IOException {
		
		ChartDisplay.fitnessHistogram("Fitness for iteration " + iteration, individuals);
		ChartDisplay.genotypeSpaceCoverage("Space coverage for iter " + iteration, individuals, "greedA",
				"enteringValue");
		// ChartDisplay.genToFitnessRelation("Gen to fitness relation "+
		// iteration, individuals, "enteringValue");

	}

	private void calculateStats() {
		stats.size = individuals.size();
		// calculate best, mean fitness, variance etc
		double fitnessSum = 0;
		for (Individual ind : individuals) {
			fitnessSum += ind.fitness;
			if (ind.fitness > stats.bestIndividual.fitness) {
				stats.bestIndividual = ind;
			}
		}
		stats.meanFitness = fitnessSum / individuals.size();

		double semiVariancePos = 0;
		double semiVarianceNeg = 0;
		for (Individual ind : individuals) {
			double diff = ind.fitness - stats.meanFitness;
			if (diff < 0)
				semiVarianceNeg += diff * diff;
			else
				semiVariancePos += diff * diff;
		}
		semiVariancePos /= individuals.size();
		semiVarianceNeg /= individuals.size();
		stats.sigmaPlus = Math.sqrt(semiVariancePos);
		stats.sigmaMinus = Math.sqrt(semiVarianceNeg);
		stats.sigma = Math.sqrt(semiVarianceNeg + semiVariancePos);
	}

	public void evaluatePopulation() {
		
		for (Individual ind : individuals) {
			ind.fitness = fitnessFun.estimate(ind.genotype, params);
		}
		
		Collections.sort(individuals);
		sortIndicator = true;
		
		stats.bestIndividual = individuals.getLast();
		
		calculateStats();
	}

	public Individual getBestIndividual() {
		return stats.bestIndividual;
	}
	
	public PopulationStats getStatistics () {
		return stats;
	}
	
	public int getIteration () {
		return iteration;
	}
	
	public FitnessFunction getFitnessFunction () {
		return fitnessFun;
	}

	public List<Individual> getNBestIndividuals(int n) {
		ArrayList<Individual> list = new ArrayList<Individual>(individuals);
		Collections.sort(list);
		return list.subList(list.size() - n, list.size());
	}

	public void setListener(PopulationListener listener) {
		this.listener = listener;
	}

	public PopulationListener getListener() {
		return listener;
	}

}
